
;(function(window, document){
	window.MergeSort = {
		sort: function(pOrgData){
			this._arr = pOrgData;
			this._rec(new Array(this._arr.length), 0, this._arr.length-1);
		},
		_rec: function(tmp, lowerBound, upperBound){
			if( lowerBound != upperBound ) {
				var mid = Math.floor((lowerBound+upperBound)/2);
				this._rec(tmp, lowerBound, mid);
				this._rec(tmp, mid+1, upperBound);
				this._merge(tmp, lowerBound, mid+1, upperBound);
			}
		},
		_merge: function(tmp, lIdx, rIdx, max){
			var i= 0,
				min = lIdx,
				middle = rIdx - 1,
				len = max - lIdx + 1;
			while( lIdx<=middle && rIdx<=max){
				if( this._arr[lIdx]<this._arr[rIdx]) tmp[i++]=this._arr[lIdx++];
				else tmp[i++]=this._arr[rIdx++];
			}
			while( lIdx<=middle ) tmp[i++] = this._arr[lIdx++];
			while( rIdx<=max ) tmp[i++] = this._arr[rIdx++];
			// 将排序结果放置到原数组中
			for(i=0;i<len;i++) this._arr[min+i]=tmp[i];
		}
	};
})(window, document);